package com.demo.linkList.loopSingleLikList;

/**
 * 单向循环链表
 */
public class LoopSingleLinkList {

    private Node firstNode;

    /**
     * 初始化链表,后一个节点指向自己
     * @param node
     */
    public LoopSingleLinkList(Node node) {
        this.firstNode = node;
        // 初始化时需要将下一个节点设置为自己（第一个节点）
        this.firstNode.setNextNode(this.firstNode);
    }

    /**
     * 初始化 nums 个节点的链表
     * @param nums
     * @return
     */
    public static LoopSingleLinkList initMultipartNode(Integer nums) {
        LoopSingleLinkList list = null;
        for (Integer i = 1; i <= nums; i++) {
            if (list == null) {
                list = new LoopSingleLinkList(new Node(i, "第" + i + "个节点"));
            } else {
                list.addNode(new Node(i, "第" + i + "个节点"));
            }
        }
        return list;
    }

    /**
     * 根据用户的输入，计算出节点出圈的顺序
     * @param startNo 从第几个节点开始数数
     * @param countNum 数几下
     * @param nums 最初有多少节点在圈中
     * 约瑟夫问题
     */
    public void countNode(int startNo, int countNum, int nums) {
        // 先对数据进行校验
        if (firstNode == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        // 创建辅助指针，帮助完成节点出圈
        Node helper = firstNode;
        // 需要创建一个辅助指针helper，事先应该指向循环链表的最后一个节点
        while (true) {
            if (helper.getNextNode() == firstNode) {
                break;
            }
            helper = helper.getNextNode();
        }
        // 节点报数前，先让first和helper移动startNo-1次
        for (int i = 0; i < startNo - 1; i++) {
            firstNode = firstNode.getNextNode();
            helper = helper.getNextNode();
        }
        // 当节点报数时，让first和helper指针同时移动countNum-1次，然后出圈
        // 这里是一个循环操作，直到圈中只有一个
        while (true) {
            // 圈中只有一个节点
            if (helper == firstNode) {
                break;
            }
            // 让firstNode和helper指针同时移动countNum-1 次
            for (int i = 0; i < countNum - 1; i++) {
                firstNode = firstNode.getNextNode();
                helper = helper.getNextNode();
            }
            // firstNode指向的就是要出圈的节点
            System.out.println("出圈的节点为：" + firstNode);
            // 将firstNode指向的节点出圈
            firstNode = firstNode.getNextNode();
            helper.setNextNode(firstNode);
        }
        System.out.println("留在圈中的节点为：" + firstNode);
    }

    /**
     * 链表遍历
     */
    public void show() {
        if (firstNode == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = firstNode;
        while (true) {
            System.out.println(temp);
            temp = temp.getNextNode();
            // 当下一个节点 == 第一个节点时，表示链表已经遍历完毕
            if (temp.getNo() == firstNode.getNo()) {
                break;
            }
        }
    }

    /**
     * 添加节点
     * @param node
     */
    public void addNode(Node node) {
        if (firstNode == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = firstNode;
        while (true) {
            if (temp.getNextNode().getNo() == firstNode.getNo()) {
                break;
            }
            temp = temp.getNextNode();
        }
        // 新插入节点的下一节点指针要设置成第一个节点
        node.setNextNode(temp.getNextNode());
        temp.setNextNode(node);
    }
}
